package earley;

import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
import java.util.TreeSet;
import java.util.concurrent.LinkedBlockingQueue;

public class Parser {
	
	/**
	 * Array of charts
	 */
	final List<List<Item>> charts;
	
	/**
	 * list of rules
	 */
	final List<Rule> rules; 
	
	final TreeSet<Item> active_predicted = new TreeSet<Item>();
	
	final Queue<Item> completedQueue = new LinkedBlockingQueue<Item>();
	
	final HashMap<Symbol, Item>[] completed;
	
	final String words;
	
	int pos = 0;
	
	/**
	 * The root of parse tree
	 */
	TreeNode root;
	
	@SuppressWarnings("unchecked")
	public Parser(String words, String[] rules) {
		charts = new ArrayList<List<Item>>(words.length());
		this.rules = parseRules(rules); 
		this.words = words;
		completed = new HashMap[words.length() + 1];
		for (int i = 0; i < completed.length; i++) {
			completed[i] = new HashMap<Symbol, Item>();
		}
	}
	
	public static void main(String[] args) {
		
		String[] input = new String[] {	"<S> ::= <E>",
										"<E> ::= <E> <Q> <F> | <F>",
										"<F> ::= a",
										"<Q> ::= x | / "};
		
		/*
		List<Rule> rules = parseRules(input);
		
		for (Rule r : rules) {
			System.out.println(r + "\n");
		}
		*/
		String words = "axa/a";
		
		Parser p = new Parser(words, input);
		
		p.parse();
		
		int i = 0;
		for (List<Item> chart : p.charts) {
			System.out.println("CHART #" + i);
			
			System.out.println("completed:");
			for (Item item : p.completed[i].values()) {
				System.out.println(item);
			}
			System.out.println();
			
			System.out.println("active/predicted:");
			for (Item item : chart) {
				System.out.println(item);
			}
			System.out.println();
			i++;
		}
	}
	
	public void parse() {
		// init
		charts.add(new LinkedList<Item>()); // initial chart
		// set active_0
		active_predicted.add(new Item(rules.get(0), 0, 0));
		// obtain itemset_0
		pos = -1;
		predictor();
		charts.get(0).addAll(active_predicted);
		active_predicted.clear();
		// go through words
		for (pos = 0; pos < words.length(); pos++) {
			System.out.println("POS: " + pos + "\t" + words.charAt(pos));
			// build active_(pos + 1) and completed_(pos + 1)
			scanner();
			// reduce completed items
			completer();
			// predict
			predictor();
			// add next chart
			charts.add(new LinkedList<Item>()); 
			charts.get(pos + 1).addAll(active_predicted);
			// clear active and predicted sets
			active_predicted.clear();
		}
		
		//System.out.println("\nBUILD TREE");
		//buildTree();
	}
	
	private void scanner() {
		// last chart
		final List<Item> chart = charts.get(charts.size() - 1);
		
		for (Item item : chart) {
			final int ruleRightSize = item.rule.right.size();
			if (item.dotPos < ruleRightSize) {
				final Symbol sym = item.rule.right.get(item.dotPos); // symbol after dot
				if (sym.isTerminal && sym.name.equals("" + words.charAt(pos))) {
					if (item.dotPos < ruleRightSize - 1) {
						active_predicted.add(new Item(item.rule, item.dotPos + 1, item.symbolPos));
					} else {
						completedQueue.add(new Item(item.rule, item.dotPos + 1, item.symbolPos));
					}
				}
			}
		}
	}
	
	
	
	private void scanner(Symbol r, int m) {
		// chart # m
		final List<Item> chart = charts.get(m);
		
		for (Item item : chart) {
			if (item.rule.right.get(item.dotPos).equals(r)) {
				final int ruleRightSize = item.rule.right.size();
				if (item.dotPos < ruleRightSize - 1) {
					active_predicted.add(new Item(item.rule, item.dotPos + 1, item.symbolPos));
				} else if (item.dotPos < ruleRightSize) {
					completedQueue.add(new Item(item.rule, item.dotPos + 1, item.symbolPos));
				}
			}
		}
	}
	
	private void completer() {
		while(!completedQueue.isEmpty()) {
			final Item item = completedQueue.poll(); // extract first
			Symbol r = item.rule.left;
			scanner(r, item.symbolPos);
			completed[pos + 1].put(item.rule.left, item);
		}
	}
	
	private void predictor() {
		final Queue<Item> q = new LinkedBlockingQueue<Item>();
		q.addAll(active_predicted);
		
		System.out.println("PREDICTOR");
		while (!q.isEmpty()) {
			final Item item = q.poll(); // get first from queue
			System.out.println("PREDICTOR: " + item);
			final int ruleRightSize = item.rule.right.size();
			if (item.dotPos < ruleRightSize) { // dot is not at the end
				final Symbol n = item.rule.right.get(item.dotPos);
				if (n.isTerminal == false) { // dot followed by non-terminal
					// search rules of type N -> P ...
					// put new items of type N -> *P...@(pos + 1)
					for (Rule r : rules) {
						if (r.left.equals(n)) {
							// add new item of type N -> *P...@(pos + 1) to predicted
							final Item newItem = new Item(r, 0, pos + 1);
							if (!active_predicted.contains(newItem)) {
								active_predicted.add(newItem);
								q.add(newItem);
							}
						}
					}
				}
			}
		}
		
		
		
	}
	
	/**
	 * Parses the array of rules presented in BNF into list{@link Rule} of rules. 
	 * @param input - array of rules in BNF
	 * @return
	 */
	private static List<Rule> parseRules(String[] input) {
		
		List<Rule> res = new LinkedList<Rule>();
		
		for (String str : input) {
			String s = str + " ";
			//System.out.println(s);
			// read left side
			if (s.charAt(0) != '<') {
				throw new IllegalArgumentException("Illegal input at string " + s);
			}
			
			int i = 1;
			for (; i < s.length() && s.charAt(i) != '>'; i++);
			
			// here s.charAt(i) must be '>'
			if (s.charAt(i) != '>') {
				throw new IllegalArgumentException("Illegal input at string " + s);
			}
			
			final Symbol left = new Symbol(s.substring(1, i), false);
			// read right sides
			int state = 0; 	// 0 - whaiting for character 
							// 1 - reading non-terminal
							// 2 - reading terminal
			int from = 0;
			Rule curRule = new Rule(left, new LinkedList<Symbol>());
			// BNF:
			// <определяемый символ> ::= <посл.1> | <посл.2> | . . . | <посл.n>
			i = s.indexOf("::=", i) + 3; // skip "::="
			s = s + " ";
			for (;i < s.length(); i++) {
				//System.out.println(state + " " + s.charAt(i));
				if (s.charAt(i) == '<') {
					if (state == 0) {
						state = 1;
						from = i + 1;
					} else {
						throw new IllegalArgumentException("Illegal input at string " + s);
					}
				} else if (s.charAt(i) == '>') {
					if (state == 1) {
						// add new non-terminal symbol to the right side of current rule
						curRule.right.add(new Symbol(s.substring(from, i), false));
						state = 0;
					} else {
						throw new IllegalArgumentException("Illegal input at string " + s);
					}
				} else if (s.charAt(i) == '|') {
					if (state == 2) {
						curRule.right.add(new Symbol(s.substring(from, i), true));
						state = 0;
					}
					res.add(curRule);
					curRule = new Rule(left, new LinkedList<Symbol>());
				} else if (!Character.isWhitespace(s.charAt(i))) {
					if (state == 0) {
						state = 2;
						from = i;
					}
				} else {
					if (state == 2) {
						curRule.right.add(new Symbol(s.substring(from, i), true));
						state = 0;
					}
				}
			}
			res.add(curRule);
		}
		return res;
	}
	
	/**
	 * Builds parse tree after parsing is over 
	 */
	private void buildTree() {
		final List<TreeNode> leaves = new LinkedList<TreeNode>();
		final Queue<TreeNode> leavesQueue = new LinkedBlockingQueue<TreeNode>();
		
		root = new TreeNode(rules.get(0).left);
		leaves.add(root);
		
		// go from the end to begin through the completed
		for (int i = completed.length - 1; i >=0; i--) {
			System.out.println("completed # " + i);
			// charge queue
			leavesQueue.addAll(leaves);
			while (!leavesQueue.isEmpty()) {
				final TreeNode node = leavesQueue.poll();
				System.out.println("node: " + node.symbol);
				if (node.symbol.isTerminal == false) {
					//Item item = completed[i].get(node.symbol);
					for (Item item : completed[i].values()) {
						if (item.rule.left.equals(node.symbol)) {
							System.out.println("found item: " + item);
							completed[i].remove(item.rule.left);
							leaves.remove(node);
							for (Symbol s : item.rule.right) {
								final TreeNode child = new TreeNode(s);
								node.children.add(child);
								leaves.add(child);
								leavesQueue.add(child);
								System.out.println("add child " + child.symbol + " to " + node.symbol);
								try {
									System.in.read();
								} catch (IOException e) {
									// TODO Auto-generated catch block
									e.printStackTrace();
								}
							}
						}
					}
				}
			}
		}
	}
}
